// Package _5_返回链表第一个入环节点 main
// @Title _5_返回链表第一个入环节点
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-01-14 16:54
// @Create  2022-01-14 16:54
package main

type LinkList struct {
	Val  int
	Next *LinkList
}

func main() {

}

/**
记住一个原则，快X2 慢X1 如果相交-> 有环，
然后 快回到开头，慢停在原地，一次一步，相遇就是入环
*/

//
//  getFirstMerge
//  @Description: 判断一个链表有没有环，如果没有环就返回空，如果有环 返回第一个入环的节点
//  @param *LinkList：
//  @return *LinkList：
//
func getFirstMerge(head *LinkList) *LinkList {
	if head == nil {
		return nil
	}
	slow, fast := head, head
	for true {
		if fast == nil || fast.Next == nil {
			return nil
		}
		fast, slow = fast.Next.Next, slow.Next
		if fast == slow {
			break
		}
	}
	// fast归零
	fast = head
	for fast != slow {
		fast, slow = fast.Next, slow.Next
	}
	return fast
}
